from imoocdb.errors import LRUError

# 理论上，当前数据库的内存使用，大约就应该是
# PAGE_SIZE * LRU_CAPACITY + 小部分其他开销 = 数据库进程总使用内容
# innodb_buffer_pool_size
LRU_CAPACITY = 100


class LRUNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value  # 在LRU中就是Page
        self.prev = None
        self.next = None
        # 额外的字段
        # 用于判断当前node是否被上层业务代码使用
        # 如果被显性pinned的话，那么就意味着，该节点暂时还不能淘汰
        self.pinned = False

    def __repr__(self):
        return f'{self.key}:{self.value}'

    def __eq__(self, other):
        if not isinstance(other, LRUNode):
            return False
        return self.key == other.key

    def __hash__(self):
        return hash(self.key)


# todo 当前LRU不是线程安全的，在面对多线程的时候要加锁
class LRUCache:
    def __init__(self, capacity=LRU_CAPACITY):
        self.capacity = capacity
        self.cache = {}
        # 我们做一个小优化，先把被淘汰的数据暂存在这里evicted
        self.evicted = []
        # LRU中的链表,这里面我们实现的是一个双向链表
        # dummy node 技巧，可以帮我们少写很多边界条件的逻辑判断 逻辑归一
        self.head = LRUNode(None, None)
        self.tail = LRUNode(None, None)
        self.head.next = self.tail
        self.tail.prev = self.head

    def put(self, key, value):
        if key in self.cache:
            # 此时相当于访问LRU中已经存在的一个节点
            # 需要把这个节点提取到最前的位置
            self._remove(self.cache[key])

        node = LRUNode(key, value)
        self.cache[key] = node
        self._add(node)
        # 开始进行淘汰判断，即超过capacity上限，需要从头部进行剔除
        if len(self.cache) > self.capacity:
            # 大于就要进行淘汰
            evicted_node = self.head.next
            while evicted_node and evicted_node.pinned:
                evicted_node = evicted_node.next

            if evicted_node is self.tail:
                # 删除刚刚插入的新node，同时报错
                self._remove(node)
                self.cache.pop(key)
                raise LRUError('no available space for current node')
            self._remove(evicted_node)
            del self.cache[evicted_node.key]
            self.evicted.append(evicted_node)

    def get(self, key):
        if key in self.cache:
            node = self.cache[key]
            # 调整节点位置
            self._remove(node)
            self._add(node)
            return node.value
        return None

    @staticmethod
    def _remove(node: LRUNode):
        """
        LRU中实现双向链表，便于删除节点，要是单链表的话，这个删除节点需要从头遍历
        """
        # 前置节点
        prev_node = node.prev
        # 后继节点
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node

    def _add(self, node):
        # 新节点从尾部插入，旧节点从头部剔除
        prev_node = self.tail.prev
        prev_node.next = node
        node.prev = prev_node
        node.next = self.tail
        self.tail.prev = node

    def pin(self, key):
        if key not in self.cache:
            raise LRUError('not found key')
        self.cache[key].pinned = True

    def unpin(self, key):
        if key not in self.cache:
            raise LRUError('not found key')
        self.cache[key].pinned = False

    def __getitem__(self, item):
        return self.get(item)

    def __setitem__(self, key, value):
        self.put(key, value)

    def __contains__(self, item):
        return item in self.cache
